using System;
using System.Collections.Generic;
using System.Text;

namespace Mono.Graph.PriorityQueue
{

    public class IndexedBinaryHeap<T> : IRangeIndexedPriorityQueue<T> where T : IComparable<T>
    {
        int[] heap;
        T[] Val;
        int[] heapIndex;
        int size;
        IComparer<T> Cmp;
        public IndexedBinaryHeap() { }
        public IndexedBinaryHeap(int SizeOfHeap)
        {
            ((IRangeIndexedPriorityQueue<int>)this).Create(SizeOfHeap);
        }

        void swap(int ind, int ind2)
        {
            int tmp = heap[ind2];
            heap[ind2] = heap[ind];
            heap[ind] = tmp;
            tmp = heapIndex[tmp];
            heapIndex[heap[ind]] = heapIndex[heap[ind2]];
            heapIndex[heap[ind2]] = tmp;
        }
        void HeapifyUp(int ind)
        {
            ind++;
            for (int ind2 = ind / 2; (ind > 1) && (Val[heap[ind - 1]].CompareTo(Val[heap[ind2 - 1]]) < 0); ind /=2, ind2 /= 2)
            {
                swap(ind - 1, ind2 - 1);
            }
        }
        void HeapifyDown(int ind)
        {
            ind++;
            for (; (ind * 2 <= size); )
            {
                int ind2= ind * 2;
                if ((ind * 2 != size)){ 
                    if(Val[heap[ind2-1]].CompareTo(Val[heap[ind2]])>0)
                        ind2++;
                }
                if(Val[heap[ind-1]].CompareTo(Val[heap[ind2-1]])>0)swap(ind-1,ind2-1);
                else break;
                ind=ind2;
            }
            /*{
                if (Val[heap[ind * 2 - 1]].CompareTo(Val[heap[ind - 1]]) < 0)
                {
                    swap(ind - 1, ind * 2 - 1);
                    ind *= 2;
                }
                else if ((ind * 2 != size) && (Val[heap[ind * 2]].CompareTo(Val[heap[ind - 1]])) < 0)
                {
                    swap(ind - 1, ind * 2);
                    ind = 2 * ind + 1;
                }
                else break;
            }*/
        }

        int IRangeIndexedPriorityQueue<T>.Size
        {
            get { return size; }
        }
        void IRangeIndexedPriorityQueue<T>.Create(int SizeOfHeap, IComparer<T> cmp)
        {
            Cmp = cmp;
            heap = new int[SizeOfHeap];
            Val = new T[SizeOfHeap];
            heapIndex = new int[SizeOfHeap];
            for (int i = 0; i < heapIndex.Length; i++) heapIndex[i] = -1;
            size = 0;
        }
        void IRangeIndexedPriorityQueue<T>.Create(int SizeOfHeap)
        {
            ((IRangeIndexedPriorityQueue<T>)this).Create(SizeOfHeap, Comparer<T>.Default);
        }
        void IRangeIndexedPriorityQueue<T>.Insert(int Key, T Value)
        {
            Val[Key] = Value;
            heap[size] = Key;
            heapIndex[Key] = size;
            
            HeapifyUp(size);
            size++;
            
        }
        void IRangeIndexedPriorityQueue<T>.DecreaseKey(int Key, T NewValue)
        {
            if((heapIndex[Key]>-1)&&(Val[Key].CompareTo(NewValue)>0))
            {
            Val[Key] = NewValue;
            HeapifyUp(heapIndex[Key]);
            }
        }
        int IRangeIndexedPriorityQueue<T>.TopKey
        {
            get
            {
 //               this.printf();
                return heap[0];
            }
        }
        T IRangeIndexedPriorityQueue<T>.TopVal
        {
            get
            {
                return Val[heap[0]];
            }
        }
        void IRangeIndexedPriorityQueue<T>.Pop()
        {
            if (size > 0)
            {
                size--;
                int tmp = heap[0];
                swap(0, size  );
                HeapifyDown(0);
                heapIndex[tmp] = -1;
            }
        }

        T IRangeIndexedPriorityQueue<T>.GetVal(int indx)
        {
            if (heapIndex[indx] > -1) return Val[indx];
            throw new IndexOutOfRangeException("there is no index :" + indx + " on heap");
        }

        void IRangeIndexedPriorityQueue<T>.SetVal(int indx, T value)
        {
            if (heapIndex[indx] > -1) ((IRangeIndexedPriorityQueue<T>)this).DecreaseKey(indx, value);
            else ((IRangeIndexedPriorityQueue<T>)this).Insert(indx, value);
        }


#if DEBUG
        private void printf() {
            Console.Write("biheap:");
            for (int i = 0; i < heap.Length;i++ )Console.Write(" "+heap[i]);
            Console.Write("\n");
        }
        string IS_VALID
        {
            get
            {
                StringBuilder ret = new StringBuilder();
                for (int i = 1; i < size;i++ )
                {
                    if(Val[heap[i]].CompareTo(Val[heap[((i+1)/2-1)]])<0)ret.AppendLine(""+i);
                }
                if (ret.Length == 0) ret.AppendLine("YES");
                return ret.ToString();
            }
        }
#endif
    }
    /*
    public class IndexedBinaryHeapNonGenericCompare<T> : IPriorityQueue<T> where T : IComparable
    {
        int[] heap;
        T[] Val;
        int[] heapIndex;
        int size;
        public IndexedBinaryHeapNonGenericCompare() { }
        public IndexedBinaryHeapNonGenericCompare(int SizeOfHeap)
        {
            ((IPriorityQueueInt)this).Create(SizeOfHeap);
        }

        void swap(int ind, int ind2)
        {
            int tmp = heap[ind2];
            heap[ind2] = heap[ind];
            heap[ind] = tmp;
            tmp = heapIndex[tmp];
            heapIndex[heap[ind]] = heapIndex[heap[ind2]];
            heapIndex[heap[ind2]] = tmp;
        }
        void HeapifyUp(int ind)
        {
            ind++;
            for (int ind2 = ind / 2; (ind > 1) && (Val[heap[ind - 1]].CompareTo(Val[heap[ind2 - 1]]) < 0); ind /= 2, ind2 /= 2)
            {
                swap(ind - 1, ind2 - 1);
            }
        }
        void HeapifyDown(int ind)
        {
            ind++;
            for (; (ind * 2 <= size); )
            {
                if (Val[heap[ind * 2 - 1]].CompareTo(Val[heap[ind - 1]]) < 0)
                {
                    swap(ind - 1, ind * 2 - 1);
                    ind *= 2;
                }
                else if ((ind * 2 != size) && (Val[heap[ind * 2]].CompareTo(Val[heap[ind - 1]])) < 0)
                {
                    swap(ind - 1, ind * 2);
                    ind = 2 * ind + 1;
                }
                else break;
            }
        }

        int IPriorityQueue<T>.Size
        {
            get { return size; }
        }
        void IPriorityQueue<T>.Create(int SizeOfHeap)
        {
            heap = new int[SizeOfHeap];
            Val = new T[SizeOfHeap];
            heapIndex = new int[SizeOfHeap];
            size = 0;
        }
        void IPriorityQueue<T>.Insert(int Key, T Value)
        {
            Val[Key] = Value;
            heap[size] = Key;
            heapIndex[Key] = size;
            HeapifyUp(size);
            size++;
        }
        void IPriorityQueue<T>.DecreaseKey(int Key, T NewValue)
        {
            Val[Key] = NewValue;
            HeapifyUp(heapIndex[Key]);
        }
        int IPriorityQueue<T>.TopKey
        {
            get
            {
                return heap[0];
            }
        }
        T IPriorityQueue<T>.TopVal
        {
            get
            {
                return Val[heap[0]];
            }
        }
        void IPriorityQueue<T>.Pop()
        {
            if (size > 0)
            {
                swap(0, size - 1);
                HeapifyDown(0);
            }
        }
    }
*/
}
